Subject: A suggestion for loop prevention...

From: [email-masked] (Scott Adams)
Date: Fri, 13 Aug 1993 15:17:02 -0400 (EDT)

To loop prevention work group:

After a bit more thought, and re-examination of RFC 1434, I`ve
thought of two distinct  DLSw connection scenarios.  One presents
little problem with looping.  The other presents the real
difficulties.

The easy connection scenario is:

Full mesh of DLSw:

           +-------+                                   +-------+
           |  S 1  |                                   |  S 2  |
           +---+---+                                   +---+---+
               |                                           |
   N1 -------+-+----                          N2  -------+-+----
             |                                           |
      +------+-------+                           +-------+------+
      |   DLSw A     |                           |   DLSw B     |
      +---+---+---+--+                           +---+---+---+--+
         /|\ /|\ /|\                                /|\ /|\ /|\
          |   |   |                                  |   |   |
          |   |   +----------------------------------+   |   |
          |   +-------------------+ +--------------------+   |
          |                        X                         |
          |   +-------------------+ +--------------------+   |
          |   |   +----------------------------------+   |   |
          |   |   |                                  |   |   |
         \|/ \|/ \|/                                \|/ \|/ \|/
      +---+---+---+--+                           +---+---+---+--+
      |   DLSw C     +<------------------------->+   DLSw D     |
      +------+-------+                           +-------+------+
             |                                           |
  N3  -------+-+----                          N4  -------+-+----
               |                                           |
           +---+---+                                   +---+---+
           |  S 3  |                                   |  S 4  |
           +-------+                                   +-------+

If End Station S 1 issues TEST or NB_NAME_QUERY (or other broadcast
frames), this will be propogated to DLSw's B, C and D as a CANUREACH
or NETBIOS_NQ packet by DLSw A.  If these DLSw do not propogate these,
or any link level packet, over another DLSw - DLSw connection, but
only sends them out on physical (LAN or SDLC) interfaces, then there
will be no looping.  Stations S 2, S 3 and S 4 will receive the
broadcast frame (as will all other stations on networks N1, N2, N3
and N4).  In this case, there's no problem.

The other scenario I've thought about is where two or more DLSw's are
connected to the same LAN or bridged LAN:

                     +-------+              +-------+
                     |  S 1  |              |  S 2  |
                     +---+---+              +---+---+
                         |                      |
             N1 -------+-+----     N2  -------+-+----
                       |                      |
                +------+-------+      +-------+------+
                |   DLSw A     |      |   DLSw B     |
                +---+---+---+--+      +---+---+---+--+
                   /|\ /|\ /|\           /|\ /|\ /|\
                    |   |   +-------------+   |   |
                    |   +-------+ +-----------+   |
                    |            X              +-+
                    |   +-------+ +---------+   |
            |      \|/ \|/                 \|/ \|/        |
            |     +-+---+--+             +--+---+-+       |
+-----+     +-----+ DLSw C |             | DLSw D +-------+   +-----+
| S 3 +-----+     +--------+             +--------+       +---+ S 4 |
+-----+     |                                             |   +-----+
            |                                             |
            |     +--------+             +--------+       |
            +-----+ Brdg A +<----------->+ Brdg B +-------+
            |     +--------+             +--------+       |
            |                                             |
           N3                                            N3'

Note that DLSw's C and D are not configured as partners.  This must be
maintained because otherwise a parallel path (and loops) exist between
networks N3 and N3'.  I suspect that this may be part of what the
authors of RFC 1434 were trying to say in the last paragraph of
section 3. Transport Connection.  The first part of this paragraph
reads:

   Two or more Data Link Switches may be attached to the same LAN,
   consisting of a number of token-ring segments interconnected by
   source-routing bridges.  In this case, a TCP connection is not
   defined between bridges attached to the same LAN.  This will allow
   using systems to select one of the possible Data Link Switches in a
   similar manner to the selection of a brige path through a
   source-routed bridged network.

This scenario presents the real problem, as a broadcast frame issued
by End Station S 1 will be sent out to both DLSW C and DLSw D, and
thus will reach network N3/N3' from two different points.  Likewise, a
broadcast frame originating on network N3/N3' will be transmitted over
two links to each of the other DLSwitches.

Choon Lee responded to my earlier comments with a furthur explanation
of the problem, including a scenario which is a variation on the
second one presented above.  In both cases the heart of the problem is
having two or more DLSwitches on the same LAN or bridged LAN.  If this
isn't done, then there is no problem.  When things are configured this
way, then there needs to be a way to prevent both DLSw from passing
LAN traffic to the same partner DLSw's, and vica-versa.

What do people think of defining a "simple" protocol whereby each DLSw
periodically announces that it exists on each LAN it is connected to,
and who its DLSw partners are (call this a "This-is-Who-I-Know, or
TWIK packet).  If a DLSw receives one of these packets it compares the
other DLSw's partners to its own set of partners.  Using some
yet-to-be-defined algorithm it selects a non-intersecting set of
partners from the union of its partners and those reported by other
DLSwitches on the same LAN.  Those selected partners it alone will
communicate with.  The other DLSwitch(es) perform the same process,
selecting their own non-intersecting set of partners.  Each DLSw flags
as not useable the DLSw-DLSw connections it has to any partner not in
its list.  When it receives a broadcast LAN frame that's to be
propogated to DLSw partners, it doesn't send it out to those marked as
unuseable.  Likewise, if it receives from a "marked" partner an SSP
packet that would normally be broadcast to its local LAN(s), it would
not do so.

These DLSw partner sets would be updated, and aged, as a result of the
periodic broadcasts from DLSw.  If a DLSw stops broadcasting, then the
other DLSws, if connected with the same DLSw partners, would include
those partners that had been "owned" by the failed DLSw.  This might
take some time (if the TWIK period is 30 seconds, and the DLSws update
their partner sets each period, then it would require 30 seconds to
recover from a lost DLSw).

A simple algorithm for selecting the exclusive sets of partners is:
Each DLSw chooses those partners only it knows about.  All partners in
common with other DLSw are divided up evenly among the number of
DLSw's that know about them, with the fractions assigned to DLSw in
order of their IP addr host numbers.  For example, if there are 45
DLSw partners known by four different DLSw on the same LAN, then the
DLSw with the lowest host number would get the first twelve in the set
(the set of partners is ordered by IP address taken as an unsigned 32
bit number), the DLSw with the next lowest host number would get the
next 11, and so on.

I suggest this because it doesn't seem as though a spanning tree
algorithm is what is needed here (see Chonn Lee's mail about mesh
networks of DLSw), and that leaves us with having to develop our own
mechanism for preventing this rather specific problem from occuring.

The main advantages of this mechanism are:

1.  It doesn't require a change to the SSP portion of DLS.  The only
    change is that the LAN interface portion of DLS must be extended
    to require this protocol.  Note that it localizes the solution to
    just the problem point, rather than distributes it across the
    entire protocol.

2.  It could be optional, if customers are educated about the
    consequences of mis-configuring DLSwitches on the same LAN.

The important disadvantages are:

1.  It requires a new LLC SAP.

2.  It is new, and therefore un-tested.
    
What do people think?  I would very much like to have something to
propose to the SIG in late September.  The idea presented above may
not be the most elegant solution to the problem, but since no one else
has proposed any solution it may be a good place to start...

Regards,

Scott

---

From: Choon Lee <[email-masked]>
Date: Mon, 16 Aug 1993 09:37:40 -0700

Some time back I have posted suggestions to deal with the looping problem, I had
suggested 2 alternatives, one using spanning tree, and the other without.
At that time, it was thought that a non spanning tree solution would take too
much work (being a nrand new protocol), and that spanning tree would be the
preferred path. 

However, it seems that forcing spanning tree onto DLSw have certain situations
that do not work, one such situation being a full mesh topology (my earlier mail).
(Incidentally, I thought about "converting" the full mesh DLSw link into
something similar to a "LAN". This would make spanning tree work in that 
topology, but I see also other instances that this would fail).

If everyone agrees that spanning tree cannot be used in solving the looping
problem, we have no choice (?) but to proceed with inventing a *simple* non-
spanning tree loop prevention protocol.

>> section 3. Transport Connection.

My concern here is that a user may not realize the N3 and N3' are bridged, and 
connect C and D as DLSw partners (N3 and N3' may be connected by a series 
of brouters). This would constitute a "misconfiguration", but shouldn't that
be detected and prevented ?

>>  The first part of this paragraph
>> reads:
>> 
In the case of parallel DLSw (in diagram above, imagine LANs N1 and N2 are
bridged, DLSw A connected only to C, and B connected only to D), C thinks that 
A is its only partner and D thinks that B is its only partner. How do they
figure out that there's a loop?

>> 2.  It is new, and therefore un-tested.
I think it would also need a new multicast address that all DLSw nodes belong
to.

>> has proposed any solution it may be a good place to start...
Yes, we should try to get a proposal on the table soon. We are running out
of time...

>> Scott

Regards,
Choon Lee
3Com Corp.